package algorithm.KMP;

import java.util.*;
import java.util.stream.Collectors;

public class KMP {
    private String pat;
    private int[][] dp;
    public static void main(String[] args) {
        String txt = "abasfagezagafnaga";
        String pat = "ag";
        System.out.println(new KMP(pat).kmpSearch(txt));
    }
    public KMP(String pat) {
        this.pat = pat;
        dp = new int[pat.length()][256];
        dp[0][pat.charAt(0)] = 1;
        int X = 0;
        for(int i=0; i<pat.length(); ++i) {
            for(int j=0; j<256; ++j) {
                dp[i][j] = pat.charAt(i) == j ? j + 1 : dp[X][j];
            }
            X = dp[X][pat.charAt(i)];
        }
    }
    //暴力法
    public static int naiveSearch(String pat, String txt) {
        for(int i=0; i<txt.length(); ++i) {
            int idx = i;
            boolean flag = true;
            for(int j=0; j<pat.length(); ++j, ++idx) {
                if(pat.charAt(j) != txt.charAt(idx)) {
                    flag = false;
                    break;
                }
            }
            if(flag == true) {
                return idx-pat.length();
            }
        }
        return -1;
    }
    //KMP匹配
    public int kmpSearch(String txt) {
        int m = pat.length(), n = txt.length();
        int j=0;
        for(int i=0; i<n; ++i) {
            j = dp[j][txt.charAt(i)];
            if(j == m) return i-m+1;
        }
        return -1;
    }
}
